// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 该文件提供基本多精度
// 字向量算术运算的Go实现。它们的后缀是_g.
// 对于没有这些例程的汇编实现的平台来说，它们是必需的。
// 该文件还包含可以在Go中充分有效地实现的基本操作。

package big

import "math/bits"

// 一个字代表一个多精度无符号整数的一个位数。
type Word uint

const (
	_S = _W / 8 // 字节字长

	_W = bits.UintSize // 字节字长
	_B = 1 << _W       // 数字基
	_M = _B - 1        // 数字掩码
)

// 对于i:=0，该文件中的许多循环的形式为
// ；i<len（z）和&i<len（x）和&i<len（y）；i++
// i<len（z）是真实条件。
// 然而，检查i<len（x）和&i<len（y）也比让编译器在循环体中进行边界检查要快；
// 值得注意的是，它甚至比提升边界检查
// 跳出循环还要快，方法是执行类似
// /u，=x[len（z）-1]，y[len（z）-1]
// 还有其他方法提升边界检查跳出循环，
// 但是编译器的BCE对它们来说还不够强大（还？）。
// 参见第164966条中的讨论。

// ---------------------------------------------------------------
// 单词的基本运算
// 
// 下面的向量运算使用这些运算。

// z1<<W+z0=x*y 
func mulWW_g(x, y Word) (z1, z0 Word) {
	hi, lo := bits.Mul(uint(x), uint(y))
	return Word(hi), Word(lo)
}

// z1<<W+z0=x*y+c 
func mulAddWWW_g(x, y, c Word) (z1, z0 Word) {
	hi, lo := bits.Mul(uint(x), uint(y))
	var cc uint
	lo, cc = bits.Add(lo, uint(c), 0)
	return Word(hi + cc), Word(lo)
}

// nlz返回x中前导零的数量。
// 。零领先是为了方便。
func nlz(x Word) uint {
	return uint(bits.LeadingZeros(uint(x)))
}

// 结果进位c为0或1。
func addVV_g(z, x, y []Word) (c Word) {
	// 此文件顶部附近的注释讨论了for循环条件。
	for i := 0; i < len(z) && i < len(x) && i < len(y); i++ {
		zi, cc := bits.Add(uint(x[i]), uint(y[i]), uint(c))
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

// 结果进位c为0或1。
func subVV_g(z, x, y []Word) (c Word) {
	// 此文件顶部附近的注释讨论了for循环条件。
	for i := 0; i < len(z) && i < len(x) && i < len(y); i++ {
		zi, cc := bits.Sub(uint(x[i]), uint(y[i]), uint(c))
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

// 结果进位c为0或1。
func addVW_g(z, x []Word, y Word) (c Word) {
	c = y
	// 此文件顶部附近的注释讨论了for循环条件。
	for i := 0; i < len(z) && i < len(x); i++ {
		zi, cc := bits.Add(uint(x[i]), uint(c), 0)
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

// ADDVWLAGE是addVW，但用于大z。
// 唯一的区别是，我们在每次迭代中检查
// 我们是否完成了进位，
// 如果是这样，则切换到更快的副本。
// 这对于大z，
// 是一个好主意，因为当z很小时，检查和函数调用的开销超过了好处。
func addVWlarge(z, x []Word, y Word) (c Word) {
	c = y
	// 此文件顶部附近的注释讨论了for循环条件。
	for i := 0; i < len(z) && i < len(x); i++ {
		if c == 0 {
			copy(z[i:], x[i:])
			return
		}
		zi, cc := bits.Add(uint(x[i]), uint(c), 0)
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

func subVW_g(z, x []Word, y Word) (c Word) {
	c = y
	// 此文件顶部附近的注释讨论了for循环条件。
	for i := 0; i < len(z) && i < len(x); i++ {
		zi, cc := bits.Sub(uint(x[i]), uint(c), 0)
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

// subvwlagle是subVW，addvwlagle是addVW。
func subVWlarge(z, x []Word, y Word) (c Word) {
	c = y
	// 此文件顶部附近的注释讨论了for循环条件。
	for i := 0; i < len(z) && i < len(x); i++ {
		if c == 0 {
			copy(z[i:], x[i:])
			return
		}
		zi, cc := bits.Sub(uint(x[i]), uint(c), 0)
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

func shlVU_g(z, x []Word, s uint) (c Word) {
	if s == 0 {
		copy(z, x)
		return
	}
	if len(z) == 0 {
		return
	}
	s &= _W - 1 // 提示编译器按s移位不需要保护代码
	ŝ := _W - s
	ŝ &= _W - 1 // 同上
	c = x[len(z)-1] >> ŝ
	for i := len(z) - 1; i > 0; i-- {
		z[i] = x[i]<<s | x[i-1]>>ŝ
	}
	z[0] = x[0] << s
	return
}

func shrVU_g(z, x []Word, s uint) (c Word) {
	if s == 0 {
		copy(z, x)
		return
	}
	if len(z) == 0 {
		return
	}
	if len(x) != len(z) {
		// 这是一个由调用方保证的不变量。
		panic("len(x) != len(z)")
	}
	s &= _W - 1 // 提示编译器按s移位不需要保护代码
	ŝ := _W - s
	ŝ &= _W - 1 // 同上
	c = x[0] << ŝ
	for i := 1; i < len(z); i++ {
		z[i-1] = x[i-1]>>s | x[i]<<ŝ
	}
	z[len(z)-1] = x[len(z)-1] >> s
	return
}

func mulAddVWW_g(z, x []Word, y, r Word) (c Word) {
	c = r
	// 此文件顶部附近的注释讨论了for循环条件。
	for i := 0; i < len(z) && i < len(x); i++ {
		c, z[i] = mulAddWWW_g(x[i], y, c)
	}
	return
}

func addMulVVW_g(z, x []Word, y Word) (c Word) {
	// 此文件顶部附近的注释讨论了for循环条件。
	for i := 0; i < len(z) && i < len(x); i++ {
		z1, z0 := mulAddWWW_g(x[i], y, z[i])
		lo, cc := bits.Add(uint(z0), uint(c), 0)
		c, z[i] = Word(cc), Word(lo)
		c += z1
	}
	return
}

// q=（x1<<W+x0-r）/y.m=楼层（（_B^2-1）/d-_B）。要求x1<y.
// 一个参考“改进的不变整数除法
// （IEEE计算机交易，2010年6月11日）”
func divWW(x1, x0, y, m Word) (q, r Word) {
	s := nlz(y)
	if s != 0 {
		x1 = x1<<s | x0>>(_W-s)
		x0 <<= s
		y <<= s
	}
	d := uint(y)
	// 我们知道
	// m=⎣（B^2-1）/d⎦-B 
	// ⎣（B^2-1）/d⎦ = m+B 
	// （B^2-1）/d=m+B+delta1 0<=delta1<=d-1）/d 
	// /B^2/d=m+B+delta2 0<=1 
	// 我们试图计算的商是
	// 商=⎣（x1*B+x0）/d⎦ 
	// /=⎣（x1*B*（B^2/d）+x0*（B^2/d））/B^2⎦ 
	// /=⎣（x1*B*（m+B+delta2）+x0*（m+B+delta2））/B^2⎦ 
	// /=⎣（x1*m+x1*B+x0）/B+x0*m/B^2+delta2*（x1*B+x0）/B^2⎦ 
	// 这三项总和的后两项介于0和1之间。
	// 所以我们可以只计算第一项，我们最多会低2。
	t1, t0 := bits.Mul(uint(m), uint(x1))
	_, c := bits.Add(t0, uint(x0), 0)
	t1, _ = bits.Add(t1, uint(x1), c)
	// 商可以是t1、t1+1或t1+2。
	// 我们将尝试t1，并在需要时进行调整。
	qq := t1
	// 计算余数r=x-d*q.
	dq1, dq0 := bits.Mul(d, qq)
	r0, b := bits.Sub(uint(x0), dq0, 0)
	r1, _ := bits.Sub(uint(x1), dq1, b)
	// 我们刚才计算的余数在B+d上有界：
	// r=x1*B+x0-d*q。
	// /=x1*B+x0-d*⎣（x1*m+x1*B+x0）/B⎦ 
	// /=x1*B+x0-d*（（x1*m+x1*B+x0）/B-alpha）0<=alpha<1 
	// /=x1*B+x0-x1*d/B*m-x1*d-x0*d/B+d*alpha 
	// /=x1*B+x0-x1*d/B*⎣（B^2-1）/d-B⎦             - x1*d-x0*d/B+d*alpha 
	// /=x1*B+x0-x1*d/B*（（B^2-1）/d-B-beta）-x1*d-x0*d/B+d*alpha 0<=beta<1 
	// /=x1*B+x1/B+x1*d+x1*d/B*B*beta-x1*d-d-x0*d-d+d*d*a-
	// /=B-d+d 
	// /=B+d 
	// 所以r1只能是0或1。如果r1是1，那么我们知道q太小了。
	// q加1，r减去d。这保证了r<B，所以我们不再需要跟踪r1。
	if r1 != 0 {
		qq++
		r0 -= d
	}
	// 如果余数仍然太大，请再次增加q。
	if r0 >= d {
		qq++
		r0 -= d
	}
	return Word(qq), Word(r0 >> s)
}

// 倒数字返回除数的倒数。rec=地板（（_B^2-1）/u-_B）。u=d1<<nlz（d1）。
func reciprocalWord(d1 Word) Word {
	u := uint(d1 << nlz(d1))
	x1 := ^u
	x0 := uint(_M)
	rec, _ := bits.Div(x1, x0, u) // /（_B^2-1）/U-_B=（_B*（_M-C）+_M）/U 
	return Word(rec)
}
